import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

//class Solution1 {
//
//       class TreeNode {
//          int val;
//          TreeNode left;
//          TreeNode right;
//          TreeNode() {}
//          TreeNode(int val) { this.val = val; }
//          TreeNode(int val, TreeNode left, TreeNode right) {
//              this.val = val;
//              this.left = left;
//              this.right = right;
//          }
//      }
//
//
//    public List<Integer> preorderTraversal(TreeNode root) {
//
//        List<Integer> list = new LinkedList<>();
//
//        Deque<TreeNode> stack = new LinkedList<>();
//
//        if(root == null){
//
//            return list;
//
//        }
//
//        TreeNode cur = root;
//
//        while(cur!=null||!stack.isEmpty()){
//
//            while(cur!=null){
//
//                list.add(cur.val);
//
//                stack.push(cur);
//
//                cur = cur.left;
//
//            }
//
//            TreeNode top = stack.pop();
//
//            cur = top.right;
//
//
//
//        }
//
//        return list;
//
//    }
//}